In electronic designs, placement determines the locations of each active element of an IC, and routing is the process of creating all the wires needed to properly connect all the placed components, while obeying the design rules of the process. The task of all routers is the same—routers are given some pre-existing polygons consisting of pins on cells and optionally some pre-routes from the placers to create geometries so that all pins assigned to different nets are connected by wires and vias, that all wires and vias assigned to different nets do not overlap, and that all design rules are obeyed. That is, a router fails when two pins on the same net that should be connected are open, when two pins on two different nets that should remain open are shorted, or when some design rules are violated during routing.
One of the early routing algorithms is the Lee algorithm, which is also commonly called the maze routing algorithm. The Lee algorithm is known to find a route if one exists. Nonetheless, the Lee algorithm is also known to be slow and memory intensive. As such, the application of Lee algorithm to electronic designs over a certain size is oftentimes impractical. One widely adopted solution for the impracticality of the Lee algorithm is the introduction of a two-level global routing, which decides the rough route for each net, followed by detailed routing. As global routing is performed on coarse grids to determine an approximate route for each wire, it is much faster than pure maze routing under the Lee algorithm. In addition to determining the rough route for each net, the objectives of global routing are typically to minimize the routing congestion and the total wirelength. After the global routing is complete, each area defined by each grid is then detailed routed.
Additionally, global routing is much faster than detailed routing and also gives good indication of the difficulty of the detailed routing problem by producing congestion maps. The degree of congestion of a g-cell may be expressed as a ratio of the routing demand to the routing capacity. It should be noted that a g-cell is also called as a global routing cell and constitutes a routing area defined by a coarse routing grid. Where there are only a few overcongested g-cells, the detailed routing may still complete by using techniques such as detours through neighboring squares or wrong-way routing which avoids the capacity limits. If there is a large number of overcongested g-cells the detailed routing may fail. Many global routers today are based upon an initial route of all nets followed by a rip-up and re-route procedure which attempts to reduce the congestion by re-routing segments of nets on overloaded edges.
Recent development in global routing adopts the methodology that, during global routing, all wires are mapped onto a coarse grid comprising larger g-cells subject to certain capacity constraints. The usual medium of communication between the IC design engineers and the foundry is through a set of design rules. These rules in the presence of RET and other manufacturing constraints have become overly restrictive. Currently, most of the design rules are hard and “digital” constraints with a few exceptions such as the timing rules; that is, these design rules must be either obeyed or violated. The design engineers are thus given a set of these design rules to comply with in devising the physical design. The foundry then evaluates how many of these design rules are violated in a particular design and returns an estimated yield based on the degree of compliance with the entire set of design rules. Moreover, since the design rules are oblivious of the design requirements or the design intent of any particular electronic circuit designs, non-selective adoption of all of the design rules are usually overly pessimistic. The prior solutions to these hard design rules have focused on the detailed routers.
Chip designers use both hard and preferred design rules. A hard rule is one that must be obeyed; a preferred rule is one that improves factors such as timing, manufacturability, or yield, but it need not be strictly obeyed. Typically, a preferred rule asks a router to make more space for wires and vias than the hard rule would. It may be impossible to route a chip using only the preferred rule because of the extra area involved. The router must decide when to honor the hard rule and when to use the preferred rule.
The design rules may be categorized into two types. The first type is called hard rules which are the design rules that must be obeyed for the IC design. The second type is called soft rules or preferred rules which improve one or more factors such as timing, manufacturability, or yield but are not required to be always met. These design rules are usually imposed by the IC fabrication processes or by performance optimization techniques. The preferred rules typically ask a router to make more space for wires and vias than the hard rules do. Nonetheless, such requests for more space for wires may render routing impossible at times because of the extra space requested. One common problem which a router faces is when both the hard rules and the preferred rules are present. Prior routing algorithms require the router to determine when to honor the hard rules and when to use the preferred rules. One prior approach is to handle the issues during detailed routing only which involves techniques such as rip-up and reroute. Another prior approach is to proceed through detailed routing and then mark certain regions as “use hard rule” based on detailed routing violations. This latter approach has oftentimes been conducted manually. The shortcoming of waiting until detailed routing is that adequate routable space is not reserved early in the process so opportunities to apply the preferred rules may be lost.
On the other hand, these increasingly complex design rules impact detailed routing, and the loss in design tool quality and productivity have resulted in increased project uncertainty and manufacturing non-recurring engineering costs (NRE costs). As the global router generally guides the detailed router and as the integrated circuit designs have become more intricate, design rules imposed by the processing or manufacturing techniques and performance optimization techniques govern the spacing and sizing of the wires. As a result, global routing has grown increasingly more complex as the integrated circuit designs and the manufacturing processes advance. For example, the representation of g-cells by simple squares with capacities have been, in many cases, replaced by representations with capacities per layer and per direction, and via capacity per layer pair.
As another example, in deep sub-micron regime, resolution enhancement techniques (RET) such as OPC (optical proximity correction) and PSM (phase shift mask) may also make routing more complicated as OPC and RET may create additional design rule violations as more wires will become fat wires. More specifically, routers are generally to observe OPC rules, especially on lower metal layers where terminals reside; this is especially important as routers may combine polygons to connect wires to pins. Also, OPC rules may produce more wiring and hence causes spacing and congestion problems. Furthermore, in incorporating the PSM technologies, phase assignment by router may also cause spacing as well as width issues. In addition, off-axis illumination (OAI) rules may produce more wiring and hence causes more spacing and congestion problems. All these RET technologies present more challenges to the global routers.
In the sub-wavelength regime, 193 nm lithography is still used in 130 nm or even 65 nm features. RET is thus significantly extended to fabricate devices with dimensions of 90 nm or less. OAI typically directs light at the photomask only at certain angles to enhance resolution of dense pitches and small features. OPC makes small alterations to the features to reduce variations in the printed features. PSM creates phase difference to enhance resolution. However, these RET techniques also cause negative impact on routing. For example, a pure-router based solution to meet the antenna rule is to limit the amount of metal connected to gate. This, however, creates more wiring, vias, and thus congestion. Another example is the design rules which make minimum line spacing a function of both the wire width and length. A wider wire will influence the spacing rule within its surroundings; and two parallel wires within certain spacing will be treated as one fat wire. This halation effect results in jogs in wiring and thus inevitably creates congestion.
In addition to the RET or lithography technologies, metal density control further contributes to the complexity of the global routing algorithm. If the global router can accommodate the metal density control rules the overall design may thus produce better estimates of parasitics.
One existing approach is to handle the issue of how to determining whether to use hard rules or soft rules during detailed routing only. This approach involves, however, laborious and often manual efforts and lacks accuracy in terms of design rule marking which inevitably causes wastes of computational resource at the routing stage. That is, some elements of human strategy and scrutiny must be applied to examine the detailed routing violations to mark the region rule. Another drawback of this approach is that adequate routing space is not reserved early in the routing process, and thus opportunities to apply the preferred rule may be lost as a result.
Another existing approach is to proceed through detailed routing and then mark certain regions as “use hard rule” based on detail routing violations. These regions are marked using a spacing checker. This drawback of this latter approach is, again, the inevitable waste of computational resource as it proceeds through the detailed routing before each region is appropriately marked. Also, the spacing checker takes time and may mark routing violations that could have been avoided if the router attempted to adhere to the preferred rule. In addition, another issue which negatively impacts the applicability of this latter approach is that most routers do not honor such a region rule.
As such, there exists a need for a method and system to determine, during global routing and before detailed routing, when to use a hard rule and when to use a preferred rule when both the hard and soft rules are present in the integrated circuit design. Various embodiments of the present invention addresses this issue.